template<typename IT = const char *>
void calcKMPNext(IT begin, int n, vector<int> & next) {
    next.assign(n + 1, 0); 
    int k = -1, i = 0;
    next[0] = -1;
    while(i < n){
        while(k >= 0 and *(begin + i) != *(begin + k)) k = next[k];
        ++i, ++k;
        if(i == n) break;
        next[i] = *(begin + i) == *(begin + k) ? next[k] : k;
    }
    next[n] = k;
    return;
}

template<typename IT = const char *>
int KMPSearch(IT t, int tn, IT p, int pn, const vector<int> & next){
    assert(pn + 1 == next.size());
    if(tn < pn) return -1;
    int tp = 0, pp = 0;
    while(tp < tn){
        if(-1 == pp or *(t + tp) == *(p + pp)) ++tp, ++pp;
        else pp = next[pp];
        if(pp == pn) return tp - pn;
    }
    return -1;
}

class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> next;
        calcKMPNext(needle.begin(), needle.length(), next);
        auto t = KMPSearch(haystack.begin(), haystack.length(), needle.begin(), needle.length(), next);
        return t;
    }
};